package problem.ej1;

import input.Problem1Input;
import instance.Instance;
import instance.InstanceEj1;

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.TreeSet;
import java.util.Vector;

import output.Problem1Output;

import problem.ej1.Ruta;

public class Ej1 {
	public static int contador_ej1; /*El contador que vamos a usar para medir el rendimiento*/
	public static int contador_ej1_kruskal;
	public static int contador_ej1_calcular_peso; 
	public static int contador_ej1_mapearAVertices; 
	public static int cantidad_vertices; 
	private static TreeSet<String_y_Id> conj_string_y_id;
	

	public static void AlgoritmoPpal(String nomarch, boolean test_rend) throws Exception {
	/**Leer del archivo y generar el grafo:**/
		
		Problem1Input entrada = new Problem1Input(nomarch);
		
		
		entrada.readFile();/*Ya tengo todas las instances en entrada.instances*/
		LinkedList<Instance> instancias = entrada.getInstances();
		LinkedList<Integer> soluciones = new LinkedList<Integer>();
		LinkedList<String> test_rend_completo = new LinkedList<String>();
		LinkedList<String> test_rend_kruskal = new LinkedList<String>();
		LinkedList<String> test_rend_mapearAVertices = new LinkedList<String>();
		LinkedList<String> test_rend_calcular_peso = new LinkedList<String>();
		Iterator<Instance> it = instancias.iterator();
		while(it.hasNext()){
			InstanceEj1 inst =(InstanceEj1) it.next();
			String origen= inst.getOrigen();
			String destino= inst.getDestino();
			int sol = 0;
			Ej1.contador_ej1 = 0; Ej1.contador_ej1_kruskal = 0; Ej1.contador_ej1_mapearAVertices = 0;
			Ej1.contador_ej1_calcular_peso = 0;

			LinkedList<Ruta> lista_adyacencia = inst.getRutas();
			if(lista_adyacencia.isEmpty()) soluciones.add(0); 
			else{
//				int tamano = lista_adyacencia.size();
				/**Generar el grafo:**/
				Vector<Eje> lista = mapearAVertices(lista_adyacencia); /*mapearAVertices me guarda la cant de vertices en cantidad_veritces*/
				int v_origen = deCiudadAVertice(origen); int v_destino = deCiudadAVertice(destino);
				Kruskal kruskis = new Kruskal(cantidad_vertices, lista,v_origen, v_destino);
				/**Aplicar el BFS modificado:**/
				int tamano = lista_adyacencia.size();
				if(v_origen>= 0 && v_destino>= 0 ) sol = kruskis.damePeso();;
					if(test_rend){
						String linea = String.valueOf(tamano) + " ";
						test_rend_completo.add(linea+String.valueOf(Ej1.contador_ej1));
						test_rend_kruskal.add(linea+String.valueOf(Ej1.contador_ej1_kruskal));
						test_rend_mapearAVertices.add(linea+String.valueOf(Ej1.contador_ej1_mapearAVertices));
						test_rend_calcular_peso.add(linea+String.valueOf(Ej1.contador_ej1_calcular_peso));
					}
					else soluciones.add(sol);
			}
			
		}
		if(!test_rend){
			Problem1Output salida = new Problem1Output(nomarch +".solucion");
			salida.escribirSolucion(soluciones);
		}
		else{
			String ArchSalida=nomarch + ".testRend";
			Problem1Output salida_comp = new Problem1Output(ArchSalida+".comp");
			salida_comp.writeTestRend(test_rend_completo);
			Problem1Output salida_krus = new Problem1Output(ArchSalida+".krus");
			salida_krus.writeTestRend(test_rend_kruskal);
			Problem1Output salida_calc = new Problem1Output(ArchSalida+".calc");
			salida_calc.writeTestRend(test_rend_calcular_peso);
			Problem1Output salida_map = new Problem1Output(ArchSalida+".map");
			salida_map.writeTestRend(test_rend_mapearAVertices);
		}
	}
	
	
	
	static int deCiudadAVertice(String ciud) {
		/* Complejidad en peor caso: O(cantidad vértices) */

		int res = -1;
		boolean termine = false;
		Ej1.contador_ej1_mapearAVertices += 4;
		Ej1.contador_ej1 += 4;
		Iterator<String_y_Id> it = conj_string_y_id.iterator();
		while(it.hasNext() && !termine){
			Ej1.contador_ej1_mapearAVertices += 4;
			Ej1.contador_ej1 += 4;
			String_y_Id sid = it.next();
			if (sid.getString().equals(ciud)) {
				Ej1.contador_ej1_mapearAVertices += 4;
				Ej1.contador_ej1 += 4;
				res = sid.getId();
				termine = true;
			}
		}
		Ej1.contador_ej1 += 1;
		Ej1.contador_ej1_mapearAVertices += 1;
		return res;
	}
static class comp_Eje implements Comparator<Eje> {
	public int compare(Eje a, Eje b) {
		//Ordena en orden descendente (de mayor a menor)
		if(a.getPeso()<b.getPeso()) return 1;
		else if(a.getPeso()==b.getPeso()) return 0;
		return -1;
	}
	
}
	
static class comp_string_y_id implements Comparator<String_y_Id> {
		
		public int compare(String_y_Id as, String_y_Id bs) {
			
			String a = as.getString();
			String b = bs.getString();
			return String.CASE_INSENSITIVE_ORDER.compare(a, b);			
	    }
	}
	
	public static Vector<Eje> mapearAVertices(LinkedList<Ruta> lista_adyacencia) {
		/*Mapea de Ciudad a vértice.
		 * 1) Obtener el conjunto de ciudades sin repetir
		 * 2) Asignar a cada una un ID (vértice)
		 * 3) Devolver la lista de ejes con ciudades cambiadas por su ID ordenadas por su campo peso en orden descendente
		 */
		/*COMPLEJIDAD: O(rutas*log(ciudades)*/
		Comparator<String_y_Id> byLexico = new comp_string_y_id();
		TreeSet<String_y_Id> set_vertices = new TreeSet<String_y_Id>(byLexico);//O(1)
		Ej1.contador_ej1_mapearAVertices += 2+3;
		Ej1.contador_ej1 += 2+3;
		
		Iterator<Ruta> it_l_ady = lista_adyacencia.iterator();//O(1)
		Ej1.contador_ej1_mapearAVertices += 4;
		Ej1.contador_ej1 += 4;
		while (it_l_ady.hasNext()) {
			Ruta rut = it_l_ady.next();
			String_y_Id sid_1 = new String_y_Id(rut.getCiudad_1(), -1);
			String_y_Id sid_2 = new String_y_Id(rut.getCiudad_2(), -1);
			set_vertices.add(sid_1);
			Ej1.contador_ej1_mapearAVertices += (int) Math.log(set_vertices.size());
			Ej1.contador_ej1 += (int) Math.log(set_vertices.size());
			set_vertices.add(sid_2);
			Ej1.contador_ej1_mapearAVertices += (int) Math.log(set_vertices.size());
			Ej1.contador_ej1 += (int) Math.log(set_vertices.size());
			
			Ej1.contador_ej1_mapearAVertices += 4;
			Ej1.contador_ej1 += 4;
			/*
			 * Agrego ambas ciudades. Si ya estaban no importa, de eso se
			 * arregla el Set internamente para no admitir elementos repetidos.
			 */
			Ej1.contador_ej1_mapearAVertices++;
			Ej1.contador_ej1++;
		}//O(log(ciudades) x rutas)
		/* Ya tengo el set con los vértices sin repetir */
		cantidad_vertices = set_vertices.size();
		Ej1.contador_ej1_mapearAVertices += 2;
		Ej1.contador_ej1 += 2;

		/* Ahora le modifico a cada String del set su parte "id" asignándoles a cada uno en orden creciente */
		Iterator<String_y_Id> it_set = set_vertices.iterator();
		Ej1.contador_ej1_mapearAVertices += 5;
		Ej1.contador_ej1 += 5;
		for(int i = 0; it_set.hasNext(); i++){
			Ej1.contador_ej1_mapearAVertices += 4;
			Ej1.contador_ej1 += 4;
			String_y_Id ver = it_set.next();
			ver.changeId(i);
			Ej1.contador_ej1_mapearAVertices++;
			Ej1.contador_ej1++;
		}
		conj_string_y_id = set_vertices;
		Ej1.contador_ej1_mapearAVertices += set_vertices.size();
		Ej1.contador_ej1 += set_vertices.size();
		Vector<Eje> res = new Vector<Eje>(lista_adyacencia.size());
		Ej1.contador_ej1_mapearAVertices += lista_adyacencia.size()+2;
		Ej1.contador_ej1 += lista_adyacencia.size()+2;
		it_l_ady = lista_adyacencia.iterator();
		while (it_l_ady.hasNext()) {
			Ej1.contador_ej1_mapearAVertices += 2;
			Ej1.contador_ej1 += 2;
			Ruta rut = it_l_ady.next();
			int pos_1 = deCiudadAVertice(rut.getCiudad_1());//O(log(ciudades))
			int pos_2 = deCiudadAVertice(rut.getCiudad_2());//O(log(ciudades))
			Ej1.contador_ej1_mapearAVertices += +2;
			Ej1.contador_ej1 += +2;
			Eje eje = new Eje(pos_1, pos_2, rut.getPeso());
			Ej1.contador_ej1_mapearAVertices += 4;
			Ej1.contador_ej1 += 4;
			res.add(eje);
		}
		Collections.sort(res, new comp_Eje());
		Ej1.contador_ej1_mapearAVertices += res.size()*(int) Math.log(res.size());
		Ej1.contador_ej1 += res.size()*(int) Math.log(res.size());
		Ej1.contador_ej1_mapearAVertices += 1;
		Ej1.contador_ej1 += 1;
		return res;

	}
	

	public static void main(String[] args) throws Exception  {
		AlgoritmoPpal("./src/resources/Tp2Ej1.in", false);

		
	}

}
